#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义炸弹结构体
struct Bomb {
    int power;  // 炸弹威力
    int delay;  // 炸弹延时时间
    int position;  // 炸弹安放位置
};

// 模拟炸弹安放和爆炸过程
int simulate(int n, vector<Bomb> &bombs) {
    int currentTime = 0;
    int currentPosition = 1;
    vector<bool> bombPlaced(bombs.size(), false);  // 标记炸弹是否已安放
    vector<bool> bombDestroyed(bombs.size(), false);  // 标记炸弹是否已被摧毁

    for (int i = 0; i < bombs.size(); ++i) {
        // 计算走到安放位置所需时间
        int moveTime = abs(bombs[i].position - currentPosition);
        currentTime += moveTime;
        currentPosition = bombs[i].position;

        // 安放炸弹
        bombPlaced[i] = true;

        // 检查是否有炸弹爆炸
        for (int j = 0; j < bombs.size(); ++j) {
            if ( bombPlaced[j] && !bombDestroyed[j] && currentTime >= bombs[j].delay ) {
                // 炸弹 j 爆炸
                for (int k = 0; k < bombs.size(); ++k) {
                    if ( k != j && bombPlaced[k] && !bombDestroyed[k] &&
                         bombs[k].position >= bombs[j].position - bombs[j].power &&
                         bombs[k].position <= bombs[j].position + bombs[j].power ) {
                        // 炸弹 k 在炸弹 j 的威力范围内，被摧毁
                        bombDestroyed[k] = true;
                    }
                }
                // 检查炸弹人是否在爆炸范围内
                if ( currentPosition >= bombs[j].position - bombs[j].power &&
                     currentPosition <= bombs[j].position + bombs[j].power ) {
                    // 炸弹人死亡，等待 1 秒复活
                    currentTime += 1;
                }
            }
        }
    }

    return currentTime;
}

int main() {
    int T;
    cin >> T;

    for (int t = 1; t <= T; ++t) {
        int n, m;
        cin >> n >> m;

        vector<Bomb> bombs(m);
        for (int i = 0; i < m; ++i) {
            cin >> bombs[i].power >> bombs[i].delay >> bombs[i].position;
        }

        int result = simulate(n, bombs);
        cout << "Case " << t << ": " << result << endl;
    }

    return 0;
}